package com.it.od.od2024;

/**
 * @author: liminghui
 * @date: 2024/1/20 0:10
 * @version: 1.0
 * @description: 求岛屿数量，面积，周围
 * 岛屿数量
 * 输入
 * grid = [
 * ['1','1','0','0','0'],
 * ['1','1','0','0','0'],
 * ['0','0','1','0','0'],
 * ['0','0','0','1','1']
 * ]
 * 输出：3
 */
public class Main5 {
    public static void main(String[] args) {
        char[][] grid = new char[4][];
        grid[0] = new char[]{'1', '1', '0', '0', '0'};
        grid[1] = new char[]{'1', '1', '0', '0', '0'};
        grid[2] = new char[]{'0', '0', '1', '0', '0'};
        grid[3] = new char[]{'0', '0', '0', '1', '1'};
        int nums = numIslands(grid);
        System.out.println(nums);
    }

    // dfs
    public static int numIslands(char[][] grid) {
        if (grid == null || grid.length == 0) {
            return 0;
        }
        int r = grid.length;
        int c = grid[0].length;
        int res = 0;
        for (int i = 0; i < r; i++) {
            for (int j = 0; j < c; j++) {
                if (grid[i][j] == '1') {
                    res++;
                    dfs(grid, i, j);
                }
            }
        }
        return res;
    }

    public static void dfs(char[][] grid, int i, int j) {
        // 判断超边界，或不是1就终止搜索
        if (i < 0 || i >= grid.length || j < 0 || j >= grid[0].length || grid[i][j] != '1') {
            return;
        }
        // 修改状态
        grid[i][j] = '2';
        // 四个方向遍历
        dfs(grid, i + 1, j);
        dfs(grid, i - 1, j);
        dfs(grid, i, j + 1);
        dfs(grid, i, j - 1);
    }

    // 求岛屿最大面积
    public static int maxAreaOfIsland(int[][] grid) {
        int r = grid.length;
        int c = grid[0].length;
        int max = 0;
        for (int i = 0; i < r; i++) {
            for (int j = 0; j < c; j++) {
                if (grid[i][j] == 1) {
                    int area = area(grid, i, j);
                    max = Math.max(max, area);
                }
            }
        }
        return max;
    }

    public static int area(int[][] grid, int i, int j) {
        // 判断超边界，或不是1就终止搜索
        if (i < 0 || i >= grid.length || j < 0 || j >= grid[0].length || grid[i][j] != 1) {
            return 0;
        }
        // 修改状态
        grid[i][j] = 2;
        return 1 + area(grid, i + 1, j) +
                area(grid, i - 1, j) +
                area(grid, i, j + 1) +
                area(grid, i, j - 1);
    }
}
